package leetcode.D600.T583;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-20 21:49:39 星期日
 */

class Solution {
    public int minDistance(String word1, String word2) {
        int[] dp = new int[word2.length()+1];
        for(int i=0; i<word2.length()+1; ++i)
            dp[i] = i;
        for(int i=0; i<word1.length(); ++i) {
            int last = i;
            dp[0] = i+1;
            for(int j=0; j<word2.length(); ++j) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    int temp = last;
                    last = dp[j+1];
                    dp[j+1] = temp;
                } else {
                    last = dp[j+1];
                    dp[j+1] = Math.min(dp[j], dp[j+1])+1;
                }
            }
        }
        return dp[dp.length-1];
    }
}
